package zuoshen_mid.class1.skill2_tableGreedy;

import org.junit.Test;

/* 
    两只绝顶聪明的羊轮流吃草
    可以一次吃个1,4,16,64颗草
    规定谁吃了最后一颗草谁就赢
*/
public class TwoEatGlass {

    public String whoWin(int n) {
        /* 
            1. 找basecase
            当n在5以下，可以直接得到解：
            n = 4: 先手
            n = 3: 先手
            n = 2: 后手
            n = 1: 先手
            n = 0: 后手
        */
        if (n < 5) {
            if (n == 0 || n == 2) {
                return "后手赢";
            } else {
                return "先手赢";
            }
        }

        int base = 1;
        while (base <= n) {
            /* 
                最难理解的地方：
                当我选择了base个草，并将指挥权交给对方
                此时dfs(n - base)实际上是对方视角的子过程
                如果对方显示“后手赢”，对于对方来说，我赢了
            */
            if (whoWin(n - base).equals("后手赢")) {
                return "先手赢";
            }
            /* 
                此时有这样的情形：n接近Integer.MAX, 而base * 4完全有可能超过Integer.MAX
                这样，外界的循环又成立了，再次进行一轮，子子孙孙无穷尽也
            */
            if (base > n / 4) {
                break;
            }
            base *= 4;
        }
        return "后手赢";
    }

    public String whoWin2(int n) {
        return n % 5 == 0 || n % 5 == 2 ? "后手赢" : "先手赢";
    }
    
    @Test
    public void test() {
        for (int i = 0; i <= 100; i++) {
            System.out.print(whoWin2(i) + "\t"); 
            if ((i + 1) % 5 == 0) System.out.println();
        }
    }
}
